import heapq

def astar(start,  # starting coordinate
          goal,   # finish coordinates
          nbhd,   # nbhd(p0) is the set of p1 in its neighborhood
          cost,   # cost(p0,p1) is actual cost of moving from p0 to p1
          heuristic):  # heuristic(p,goal) estimates cost from p to goal
  """Generalized implementation of A* pathfinding. Returns a list of
  coordinates demonstrating the cheapest path from start to goal."""
  closed = set()
  q = []
  heapq.heappush(q, (0+heuristic(start,goal), [(start,0)]))
  while q:
    fp,p = heapq.heappop(q)
    x,gx = p[-1]
    if x in closed:
      continue
    if x == goal:
      return [x for (x,g) in p]
    closed.add(x)
    for y in nbhd(x):
      if y not in closed:
        gy = gx + cost(x, y)
        hy = heuristic(y, goal)
        heapq.heappush(q, (gy+hy, p + [(y,gy)]))
  return None  # failure
  
